# -*- coding: utf-8 -*-

"""1637. 两点之间不包含任何点的最宽垂直区域
给你 n 个二维平面上的点 points ，其中 points[i] = [xi, yi] ，请你返回两点之间内部不包含任何点的 最宽垂直区域 的宽度。
垂直区域 的定义是固定宽度，而 y 轴上无限延伸的一块区域（也就是高度为无穷大）。 最宽垂直区域 为宽度最大的一个垂直区域。
请注意，垂直区域 边上 的点 不在 区域内。

示例 1：
输入：points = [[8,7],[9,9],[7,4],[9,7]]
输出：1
解释：红色区域和蓝色区域都是最优区域。

示例 2：
输入：points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
输出：3

提示：
n == points.length
2 <= n <= 105
points[i].length == 2
0 <= xi, yi <= 109"""

class Solution:
    """宽度只跟横坐标有关，最大宽度，就是在有序的横坐标序列最大的间距。
    那解法就太多了，就看使用何种排序算法。看他是个中等题，我们试试堆排序"""
    def maxWidthOfVerticalArea(self, points: list) -> int:
        points = list(set([p[0] for p in points]))

        heap = []

        def heapify(its):
            for item in its:
                heappush(item)

        def heappush(item):
            i = len(heap)
            heap.append(item)

            parent = get_parent_index(i)

            while True:
                if parent == None:
                    break

                if heap[parent] <= heap[i]:
                    break

                heap[parent], heap[i] = heap[i], heap[parent]

                i = parent
                parent = get_parent_index(i)

        def heappop():
            rs = heap[0]

            last = heap.pop()

            if not heap:
                return rs

            heap[0] = last

            i = 0
            left, right = i*2+1, (i+1)*2

            while True:
                if left < len(heap) and right < len(heap):
                    if heap[i] <= heap[left] and heap[i] <= heap[right]:
                        break
                    if heap[i] > heap[left] and heap[left] <= heap[right]:
                        heap[i], heap[left] = heap[left], heap[i]
                        i = left
                    elif heap[i] > heap[right] and heap[right] <= heap[left]:
                        heap[i], heap[right] = heap[right], heap[i]
                        i = right
                elif left < len(heap):
                    if heap[i] > heap[left]:
                        heap[i], heap[left] = heap[left], heap[i]
                    break
                else:
                    break

                left, right = i*2+1, (i+1)*2

            return rs

        def get_parent_index(i):
            if i%2 == 0:
                parent = i//2-1
            else:
                parent = (i-1)//2
            return None if parent < 0 else parent
        
        heapify(points)

        max_width = 0
        x1 = heappop()
        while True:
            try:
                x2 = heappop()
                max_width = max((x2-x1), max_width)
                x1 = x2
            except IndexError:
                break

        return max_width

if __name__ == '__main__':
    print(Solution().maxWidthOfVerticalArea([[8,7],[9,9],[7,4],[9,7]]))
    print(Solution().maxWidthOfVerticalArea([[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]))
    # print(Solution().maxWidthOfVerticalArea())
